//
//  ProblemOffer06.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/9.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 06. 从尾到头打印链表
 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

 示例 1：
    输入：head = [1,3,2]
    输出：[2,3,1]

 限制：
    0 <= 链表长度 <= 10000
 */
@objcMembers class ProblemOffer06: NSObject {
    func solution() {
        let root = ListNode(1)
        root.next = ListNode(2)
        root.next?.next = ListNode(3)
        root.next?.next?.next = ListNode(4)
        root.next?.next?.next?.next = ListNode(5)
        print(reversePrintStack(root))
    }
    
    /*
     输入插入：
     每次插入到数组中
     */
    func reversePrintInsertArray(_ head: ListNode?) -> [Int] {
        var result: [Int] = []
        var node = head
        while node != nil {
            result.insert(node!.val, at: 0)
            node = node?.next
        }
        return result
    }
    
    /*
     翻转链表，然后遍历
     */
    func reversePrintStack(_ head: ListNode?) -> [Int] {
        var n: Int = 0
        var node = head
        var pre: ListNode? = nil
        while node != nil {
            let next = node?.next
            node?.next = pre
            pre = node
            node = next
            n += 1
        }
        
        var i = 0
        var result: [Int] = Array(repeating: 0, count: n)
        while pre != nil {
            result[i] = pre!.val
            pre = pre?.next
            i += 1
        }
        return result
    }
    
    
    
}
